package william.basicsort;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/1/17
 * @description 选择排序
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(20, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        SelectionSort selectionSort = new SelectionSort();
        selectionSort.selectionSort(arr);
        System.out.println("排序后数组为: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("数组是否按照升序排列: " + ArrayUtils.isInAscOrder(arr));
    }

    /**
     * 第一轮:找到数组中最小的元素,与数组的第一个元素进行交换
     * 第二轮:找到数组中第二小的元素,与数组的第二个元素进行交换
     * 重复上述步骤,直到整个数组有序
     */
    public void selectionSort(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length == 0) {
            return;
        }

        int N = arr.length;

        for (int i = 0; i < N; i++) {  //外层i控制是第几轮操作
            int minIndex = i;

            for (int j = i; j < N; j++) {    //内存j用于遍历数组找到当前最小值
                //找到当前最小值
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            //将最小值与当前首位元素进行交换
            ArrayUtils.swap(arr, i, minIndex);
        }
    }
}
